import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=15 lang=java
 *
 * [15] 三数之和
 *
 * https://leetcode-cn.com/problems/3sum/description/
 *
 * algorithms
 * Medium (24.79%)
 * Likes:    1632
 * Dislikes: 0
 * Total Accepted:    132.9K
 * Total Submissions: 535.9K
 * Testcase Example:  '[-1,0,1,2,-1,-4]'
 *
 * 给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0
 * ？找出所有满足条件且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 *
 * 例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
 *
 * 满足要求的三元组集合为：
 * [
 * ⁠ [-1, 0, 1],
 * ⁠ [-1, -1, 2]
 * ]
 *
 *
 */

// @lc code=start
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer> set = new HashMap<>();
        Set<Integer> repeat = new HashSet<>();
        for(int index=0;index<nums.length;index++) {
            if(nums[index] < 0 && !repeat.contains(nums[index])) {
                int sum = -nums[index];
                set.clear();
                for(int i=0;i<nums.length;i++) {
                    if(i == index) {
                        continue;
                    }
                    if (set.contains(sum- nums[i])) {
                        result.add(Arrays.asList(nums[index], nums[i], sum- nums[i]));
                        repeat.add(nums[index]);
                    } else {
                        set.add(nums[i]);
                    }
                }
            }
        }
        return result;
    }
}
// @lc code=end

